package com.logbug;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

public class Exam {
    public static void main(String[] args) {

        System.out.println("第一题：");
        new Part1().printResult();
        System.out.println("第二题：");
        new Part2().printResult();
    }
}

interface Part {
    public void printResult();

}

/**
 * 问题：
 * 某企业拥有4条流水生产线A、B、C、D，每条流水线目前每月的生产量在10、7、 5、4吨。现企业需要优化各流水线，故实行每月末从生产最多的流水线中抽出3吨 的生产力，分配到剩余的3条流水线里，既其余每条流水线多生产1吨，这称为一次 生产力优化(既经过第一个月后的优化，各流水线生产吨数在:7、8、6、5)
 * 那么请问，经过五年的生产力优化调整后，哪个流水线生产力最高，可每月生产多 少吨
 * 编程求解该问题，并思考是否为最优解。
 * <p>
 * 算法：
 * 一、循环5*12+1个月次，每次调整生产线的生产力
 * 二、一次调整过程如下：
 * 1.增加每个生产线的生产力(处于性能考虑，这样设计可以只用一趟for循环)。
 * 2.找出最大生产力的生产线。
 * 3.使最大生产力的生产线的生产力减少
 */
class Part1 implements Part {
    // 存放生产线的数组
    WorkLine[] lines = new WorkLine[4];

    public Part1() {
        // 初始化生产线数组
        lines[0] = new WorkLine("A", 10);
        lines[1] = new WorkLine("B", 7);
        lines[2] = new WorkLine("C", 5);
        lines[3] = new WorkLine("D", 4);
    }

    /**
     * 打印结果
     */
    public void printResult() {
        WorkLine maxLine = null;
        // 这里需要循环5年加一个月次，返回的才是第五年结束后的最大生产力的生产线对象
        for (int i = 0; i < 5 * 12 + 1; i++) {
            maxLine = adj();
        }
        // 这里maxLine的power已经被减少了，所以在输出时要得到修正的值。
        System.out.printf("流水线 %s 的生产力最高，可每月生产 %d 吨", maxLine.name, maxLine.getMaxPower());
        System.out.println();
    }

    /**
     * 调整生产力
     *
     * @return 返回上个月最大生产力的生产线对象，注意此时的power时经过减小了的值
     */
    public WorkLine adj() {
        // 取出第一个生产线作为最大值
        WorkLine maxLine = lines[0];
        // 增加生产力
        maxLine.increase();
        for (int i = 1; i < lines.length; i++) {
            WorkLine line = lines[i];
            line.increase();
            // 求最大值
            if (line.power > maxLine.power) {
                maxLine = line;
            }
        }
        maxLine.reduce();
        return maxLine;
    }
}

class WorkLine {
    String name;
    int power;

    public WorkLine(String name, int power) {
        this.name = name;
        this.power = power;
    }

    public void reduce() {
        power = power - 4;
    }

    public int getMaxPower() {
        return power += 3;
    }


    public void increase() {
        power++;
    }
}

/**
 * 问题：
 * 给定一个数组，例如[15, 2, 8, 13]，找到符合下面方式的结果，并打印出来 例如: 1)从数组每位元素当前位置开始，往后找到大于自己本身的第一位元素，并返回 1)如果没有找到，返回-1
 * 结果如下
 * 15 -> -1
 * 2 -> 8
 * 8 -> 13
 * 13 -> -1
 * <p>
 * 算法：
 * 使用嵌套for循环在第一层for循环中查找当前元素往后大于本身的第一位元素
 * 时间复杂度： O((n^2)/2)
 * 最坏情况：数组倒序排列
 */
class Part2 implements Part {
    int[] arr = new int[]{15, 2, 8, 13};

    public void getFirstBiggerOne() {
        for (int i = 0; i < arr.length; i++) {
            int current = arr[i];
            int result = -1;
            for (int j = i + 1; j < arr.length; j++) {
                int next = arr[j];
                if (current < next) {
                    result = next;
                    break;
                }
            }
            System.out.printf("%d -> %d", current, result);
            System.out.println();
        }
    }

    public void printResult() {
        getFirstBiggerOne();
    }
}



/*
 * 第四题(选答)
 * 有两组数，第一组数顺序固定，请编程实现让第二组数 相邻数字间的大小关系和第一 组数相同，且
 * 第二组相邻数字间的差值之和最大
 * 下面给出一个示例
 * 第一组数: 5 7 4 9
 * 第二组数:1 2 3 4
 * 第二组数排序结果:2 4 1 3
 * 第二组数排序后的差值之和:7 = abs(2-4) + abs(4-1) + abs(1-3)
 * */

class Part4 implements Part {
    Node[] templateArr = new Node[]{new Node(5), new Node(7), new Node(4), new Node(9)};

    Node[] nodeArr = new Node[]{new Node(1), new Node(2), new Node(3), new Node(4)};

    Node[] longestPath = new Node[nodeArr.length];

    Path templatePath = new Path();

    public Part4() {
        initTemplate();
        makeGraph();
        findLongestPath();
    }

    void initTemplate() {


        // 构造模版路径
        for (int i = 0; i < templateArr.length; i++) {
            Node node = templateArr[i];
            Node nextNode;
            if (i != templateArr.length - 1) {
                // 不是最后一个节点
                nextNode = templateArr[i + 1];
                Node start, end;
                int direction;
                if (node.value > nextNode.value) {
                    start = nextNode;
                    end = node;
                    direction = PathElement.BACKWARD;
                } else {
                    start = node;
                    end = nextNode;
                    direction = PathElement.FORWARD;

                }
                Line line = new Line(start, end);
                templatePath.addLine(direction, line);
                node.addOutLine(line);
                nextNode.addInLine(line);

            }
        }
    }

    void makeGraph() {
        // 构造有向图
        for (int i = 0; i < nodeArr.length; i++) {
            Node start = new Node(i);
            for (int j = 0; j < nodeArr.length; j++) {
                Node end = nodeArr[j];
                if (i != j && start.value < end.value) {
                    Line line = new Line(start, end);
                    start.addOutLine(line);
                    end.addInLine(line);
                }
            }
        }
    }

    PathStack stack=new PathStack();
    void findLongestPath() {
        for (int i = 0; i < nodeArr.length; i++) {
            Node node = nodeArr[i];
            Iterator<PathElement> iterator = templatePath.iterator();

            loopNode(node, iterator);


        }
    }

    private void loopNode(Node node, Iterator<PathElement> iterator) {
        if (iterator.hasNext()) {
            PathElement pathElement = iterator.next();
            List<Line> lines;
            if (pathElement.direction == PathElement.FORWARD) {
                lines = node.outLine;
            } else {
                lines = node.inLine;
            }
            if (lines.size() > 0) {
                // 这条路经可以继续下去
                for (Line line : lines) {
                    Node nextNode;
                    if (pathElement.direction == PathElement.FORWARD) {
                        nextNode = line.end;
                    } else {
                        nextNode = line.start;
                    }
                    // 向路径栈中添加元素
                    stack.push(line);

                    loopNode(nextNode, iterator);
                }
            }

        }

    }


    @Override
    public void printResult() {

    }
}

class Node {
    int value;
    List<Line> outLine;
    List<Line> inLine;

    public Node(int value) {
        this.value = value;
        outLine = new ArrayList<>();
        inLine = new ArrayList<>();
    }

    public void addOutLine(Line line) {
        this.outLine.add(line);
    }

    public void addInLine(Line line) {
        this.inLine.add(line);
    }

    public boolean hasBiggerNext() {
        return this.outLine.size() > 0;
    }

    public boolean hasSmallerNext() {
        return this.inLine.size() > 0;
    }

}

// 矢量
class Line {
    // 开始节点比结束节点小的差值
    int wight;
    Node start;
    Node end;

    public Line(Node start, Node end) {
        this.start = start;
        this.end = end;

        this.wight = end.value - start.value;
    }
}

class Path {
    int totalWight = 0;
    List<PathElement> elements = new ArrayList<>();

    public void addLine(int direction, Line line) {
        elements.add(new PathElement(direction, line));
        totalWight += line.wight;
    }

    public int getPathLength() {
        return elements.size();
    }

    public Iterator<PathElement> iterator() {
        return elements.iterator();
    }
}

class PathElement {
    public static int FORWARD = 1;
    public static int BACKWARD = -1;
    int direction;
    Line line;

    public PathElement(int direction, Line line) {
        this.direction = direction;
        this.line = line;
    }
}

class PathStack {
    StackElement element;

    public void push(Line node) {
        StackElement stackElement = new StackElement(node);
        stackElement.prev = element;
        element = stackElement;
    }

    public Line pop() {
        Line line = this.element.value;
        element = null;
        return line;
    }

    public boolean empty() {
        return element == null;
    }

}

class StackElement {
    Line value;
    StackElement prev;

    public StackElement(Line value) {
        this.value = value;
    }

}
